﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace GKS.Extensions.String.EditDistance {
    
    /// <summary>
    /// A class that contains the tools necessary to measure the edit distance of two strings.
    /// </summary>
    public static class EditDistanceExtension {
        private static Dictionary<Operation, char> operationChar = new Dictionary<Operation, char>(){
            { Operation.Insert,     'I' },
            { Operation.Delete,     'D' },
            { Operation.Match,      'M' },
            { Operation.Replace,    'R' }
        };

        public enum Operation{
            Insert,
            Delete,
            Match,
            Replace
        };

        public static Dictionary<Operation, char> OperationChar {
            get {
                return operationChar;
            }
        }

        public static Dictionary<Operation, int> OperationWeights { get; set; }

        public static int GetEditDistance(this string first, string second, int[,] editDistanceMatrix = null) {
            return (editDistanceMatrix != null && editDistanceMatrix.GetLength(0) == first.Length + 1 && editDistanceMatrix.GetLength(1) == second.Length + 1) 
                        ? editDistanceMatrix[first.Length, second.Length]
                        : first.GetEditDistanceMatrix(second)[first.Length, second.Length];
        }

        public static string[] GetEditTransformations(this string first, string second, int[,] editDistanceMatrix = null) {
            List<string> transformations = new List<string>();
            int[,] matrix = (editDistanceMatrix != null && editDistanceMatrix.GetLength(0) == first.Length + 1 && editDistanceMatrix.GetLength(1) == second.Length + 1)
                                ? editDistanceMatrix
                                : first.GetEditDistanceMatrix(second);

            first.GetPaths(second, matrix, first.Length, second.Length, "", ref transformations);

            return transformations.ToArray();
        }

        public static int[,] GetEditDistanceMatrix(this string first, string second) {
            int[,] editDistanceMatrix = new int[first.Length + 1, second.Length + 1];
            int dWeight,        // deletion weight
                oWeight,        // replacement or matching weight (depending on the case)
                iWeight;        // insertion weight
            
            InitializeEditDistanceMatrix(first, second, editDistanceMatrix);

            // set values in the other elements of the matrix
            for (int i = 1; i <= first.Length; i++) {
                for (int j = 1; j <= second.Length; j++) {
                    dWeight = editDistanceMatrix[i - 1, j] + (OperationWeights != null && OperationWeights.Keys.Contains(Operation.Delete) ? OperationWeights[Operation.Delete] : 1);
                    iWeight = editDistanceMatrix[i, j - 1] + (OperationWeights != null && OperationWeights.Keys.Contains(Operation.Insert) ? OperationWeights[Operation.Insert] : 1);

                    oWeight = (first.ElementAt(i - 1).Equals(second.ElementAt(j - 1)))
                        ? editDistanceMatrix[i - 1, j - 1] + (OperationWeights != null && OperationWeights.Keys.Contains(Operation.Match) ? OperationWeights[Operation.Match] : 0)
                        : editDistanceMatrix[i - 1, j - 1] + (OperationWeights != null && OperationWeights.Keys.Contains(Operation.Replace) ? OperationWeights[Operation.Replace] : 1);

                    editDistanceMatrix[i, j] = Math.Min(dWeight, Math.Min(iWeight, oWeight));
                }
            }

            return editDistanceMatrix;
        }

        private static void InitializeEditDistanceMatrix(string first, string second, int[,] editDistanceMatrix) {
            // initialize the first column
            for (int i = 0; i <= first.Length; i++) {
                editDistanceMatrix[i, 0] = i + (OperationWeights != null && OperationWeights.Keys.Contains(Operation.Delete) ? OperationWeights[Operation.Delete] - 1 : 0);
            }

            // initialize the first row
            for (int i = 0; i <= second.Length; i++) {
                editDistanceMatrix[0, i] = i + (OperationWeights != null && OperationWeights.Keys.Contains(Operation.Insert) ? OperationWeights[Operation.Insert] - 1 : 0);
            }
        }

        private static void GetPaths(this string first, string second, int[,] editDistanceMatrix, int i, int j, string currentTransformation, ref List<string> transformations) {
            if (i > 0 && j > 0) {
                if (first.ElementAt(i - 1).Equals(second.ElementAt(j - 1)) 
                    && editDistanceMatrix[i - 1, j - 1] == editDistanceMatrix[i, j] - (OperationWeights != null && OperationWeights.Keys.Contains(Operation.Match) ? OperationWeights[Operation.Match] : 0)
                ) {
                        first.GetPaths(second, editDistanceMatrix, i - 1, j - 1, OperationChar[Operation.Match].ToString() + currentTransformation, ref transformations);
                }

                if (editDistanceMatrix[i - 1, j - 1] == editDistanceMatrix[i, j] - (OperationWeights != null && OperationWeights.Keys.Contains(Operation.Replace) ? OperationWeights[Operation.Replace] : 1)) {
                    first.GetPaths(second, editDistanceMatrix, i - 1, j - 1, OperationChar[Operation.Replace].ToString() + currentTransformation, ref transformations);
                }

                if (editDistanceMatrix[i - 1, j] == editDistanceMatrix[i, j] - (OperationWeights != null && OperationWeights.Keys.Contains(Operation.Delete) ? OperationWeights[Operation.Delete] : 1)) {
                    first.GetPaths(second, editDistanceMatrix, i - 1, j, OperationChar[Operation.Delete].ToString() + currentTransformation, ref transformations);
                }

                if (editDistanceMatrix[i, j - 1] == editDistanceMatrix[i, j] - (OperationWeights != null && OperationWeights.Keys.Contains(Operation.Insert) ? OperationWeights[Operation.Insert] : 1)) {
                    first.GetPaths(second, editDistanceMatrix, i, j - 1, OperationChar[Operation.Insert].ToString() + currentTransformation, ref transformations);
                }
            } else if (i > 0) { // j == 0
                first.GetPaths(second, editDistanceMatrix, i - 1, j, OperationChar[Operation.Delete].ToString() + currentTransformation, ref transformations);
            } else if (j > 0) { // i == 0
                first.GetPaths(second, editDistanceMatrix, i, j - 1, OperationChar[Operation.Insert].ToString() + currentTransformation, ref transformations);
            } else {    // i == 0 && j == 0
                transformations.Add(currentTransformation);
            }
        }
    }
}
